from collections import defaultdict, deque


class Solution:
    def numberOfSubstrings(self, s: str, k: int) -> int:
        mp = defaultdict(deque)
        ans = 0
        for i, v in enumerate(s):
            mp[v].append(i)
            if len(mp[v]) > k:
                mp[v].popleft()
            mx = -1
            for j in mp.keys():
                if len(mp[j]) == k:
                    mx = max(mx, mp[j][0])
            ans += mx + 1
        return ans


so = Solution()
print(so.numberOfSubstrings(s="abacb", k=2))
